#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* _merge(ListNode* head1, ListNode* head2)
    {
        if (head1 == nullptr && head2 != nullptr)
            return head2;
        if (head1 != nullptr && head2 == nullptr)
            return head1;
        ListNode* cur, * PHead;
        PHead = cur = new ListNode(-1);
        while (head1 && head2)
        {
            if (head1->val < head2->val)
            {
                cur->next = head1;
                head1 = head1->next;
            }
            else
            {
                cur->next = head2;
                head2 = head2->next;
            }
            cur = cur->next;
        }
        cur->next = head1 != nullptr ? head1 : head2;
        cur = PHead;
        PHead = PHead->next;
        delete cur;
        return PHead;
    }
    ListNode* _mergeKLists(vector<ListNode*>& lists, int left, int right)
    {
        if (left == right)
            return lists[left];
        if (left > right)
            return nullptr;
        int mid = (left + right) / 2;
        return _merge(_mergeKLists(lists, left, mid), _mergeKLists(lists, mid + 1, right));
    }
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        return _mergeKLists(lists, 0, lists.size() - 1);
    }
};

